package mao.leetcode.offer;

/**
 * @author Totoro
 * @date 2020/8/6
 * @explain:
 */
public class interview47 {
    static class Solution {
        public int maxValue(int[][] grid) {
            int m = grid.length,n = grid[0].length;

            int[] dp = new int[n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if( j == 0){
                        dp[j] = dp[j]+grid[i][j];
                    }else{
                        dp[j] = Math.max(dp[j],dp[j-1])+grid[i][j];
                    }
                }

            }
            return dp[n-1];
        }


    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] arr ={{1,3,1},{1,5,1},{4,2,1}};
        solution.maxValue(arr);
    }
}
